#include "big_integer.hpp"

#include <iostream>
#include <iterator>
#include <vector>
#include <list>
#include <deque>
#include <cstdarg>

using namespace std;

BIG_NUMBERS_NAMESPACE_USING;

/**
  Define a very simple testing mini-framework first
 */
#define PRINTER cerr

#ifdef NDEBUG
 #define PRINT0(x)
 #define PRINT_ARR(b, e)
#else // NDEBUG
 #define PRINT0(x) do { PRINTER << x; } while (0)
 #define PRINT_ARR(b, e) do { copy(b, e, ostream_iterator<int>(PRINTER, ", ")); } while (0)
#endif // NDEBUG
#define PRINT(x) PRINT0(x << endl)

#define TEST(condition) do { PRINT("Checking " << #condition); DO_ASSERT(condition); } while (0)

#define ARRAY_OF(arr) (sizeof (arr) /sizeof (arr)[0])
#define ARRAY_END(arr) ((arr) + ARRAY_OF(arr))

template <typename traits>
class integer_test
{
public:
        integer_test();
        void test();

private:
        typedef uinteger<traits> uinteger;
        typedef typename traits::base_type base_type;
        typedef typename traits::digit digit;
        typedef typename traits::double_digit double_digit;

        typedef typename traits::digits digits;

        typedef typename traits::char_type char_type;
        typedef typename traits::base_type::size_type size_type;
        typedef typename traits::string string;

        static const digit max_digit = uinteger::max_digit;

private:
        void test_static();
        void test_construct();
        void test_increment();
        void test_add();
        void test_sub();

        void test_rel();
        void test_rel(const uinteger&);
        void test_rel(const uinteger&, const uinteger&);

        void test_mul_digit();
        void test_from_string();
        void test_div_digit();
        void test_to_string();
        void test_div();

private:
        typedef uinteger (uinteger::*int_op)(const uinteger&) const;
        void test_op(int_op op, const uinteger& i1, const uinteger& i2, bool sym, size_t size, ...);
        void test_op(int_op op, const uinteger& i1, const uinteger& i2, const uinteger& r, bool sym);
        void test_div_0(const uinteger& u);
        void test_0_div(const uinteger& u);
        void test_div_1(const uinteger& u);
        void test_string(const string& s);
        void test_from_string_throws(const string&);


private:
        const uinteger int_f;
        const uinteger& int_ff;
        uinteger int_ff_impl;
        uinteger int_10_impl;
        const uinteger& int_10;
        uinteger int_100_impl;
        const uinteger& int_100;
        static const digit dig_0 = digit(0);
        static const digit dig_1 = digit(1);
};

bool test_mul();
bool test_div();
bool test_rsa();

int main()
{
        PRINT("\nTesting vector:10 base:unsigned short...");
        integer_test<integer_short_vector_10_traits>().test();

        PRINT("\nTesting vector:65536 base:unsigned short...");
        integer_test<integer_short_vector_ff_traits>().test();

        typedef integer_traits<unsigned short,
                std::deque<unsigned short>, unsigned int, 10, char>
                integer_short_deque_10;
        PRINT("\nTesting deque:10 base:unsigned short...");
        integer_test<integer_short_deque_10>().test();

        typedef integer_traits<unsigned short,
                std::deque<unsigned short>, unsigned int, 65536, char>
                integer_short_deque_ff;
        PRINT("\nTesting deque:65536 base:unsigned short...");
        integer_test<integer_short_deque_ff>().test();

        typedef integer_traits<unsigned short,
                std::list<unsigned short>, unsigned int, 10, char>
                integer_short_list_10;
        PRINT("\nTesting list:10 base:unsigned short...");
        integer_test<integer_short_list_10>().test();

        typedef integer_traits<unsigned short,
                std::list<unsigned short>, unsigned int, 65536, char>
                integer_short_list_ff;
        PRINT("\nTesting list:65536 base:unsigned short...");
        integer_test<integer_short_list_ff>().test();


        PRINT("\nRandom testing...");
        PRINT("\n\nTesting multiplication...");
        TEST(test_mul());
        PRINT("\n\nTesting Division...");
        TEST(test_div());
        PRINT("\n\nTesting modular exponentation computation...");
        TEST(test_rsa());
        PRINT("\n\nAll tests finisihed successfully");
        return 0;
}


template <typename It>
void dump_range(It i1, It i2)
{
        PRINT0("{");
        PRINT_ARR(i1, i2);
        PRINT0(distance(i1, i2) << "}");
}

template <typename traits>
void dump_int(const uinteger<traits>& u)
{
        dump_range(u.data_begin(), u.data_end());
}


template <typename It1, typename It2>
bool ranges_equal(It1 i1, It1 i2, It2 j1, It2 j2)
{
        PRINT0("\tCheck if equal: ");
        dump_range(i1, i2);
        dump_range(j1, j2);
        PRINT("");

        for (; i1 != i2 && j1 != j2 && *i1 == *j1; ++i1, ++j1);
        return i1 == i2 && j1 == j2;
}

template <typename traits>
void TEST_EQUAL_INT(const uinteger<traits>& i, const uinteger<traits>& j)
{
        PRINT0("\tCheck if equal: ");
        dump_int(i);
        dump_int(j);
        PRINT("");
        TEST(i == j);
}

template <typename traits>
void test_equal_arr(const uinteger<traits>& x, const typename uinteger<traits>::digits& arr)
{
        TEST(ranges_equal(x.data_begin(), x.data_end(), arr.begin(), arr.end()));
}

template <typename traits>
const typename uinteger<traits>::digits vmake_digits(size_t size, va_list list)
{
        typename uinteger<traits>::digits arr;
        while (size-- > 0)
        {
                typename traits::digit d = va_arg(list, int);
                arr.push_back(d);
        }
        return arr;
}

template <typename traits>
const typename uinteger<traits>::digits make_digits(size_t size, ...)
{
        va_list list;
        va_start(list, size);
        const typename uinteger<traits>::digits arr = vmake_digits<traits>(size, list);
        va_end(list);
        return arr;
}

template <typename traits>
void test_equal_digits(const uinteger<traits>& x, size_t size, ...)
{
        va_list list;
        va_start(list, size);
        const typename uinteger<traits>::digits arr = vmake_digits<traits>(size, list);
        va_end(list);
        test_equal_arr(x, arr);
}

template <typename traits>
integer_test<traits>::integer_test():
        int_f(uinteger(max_digit)),
        int_ff(int_ff_impl),
        int_10(int_10_impl),
        int_100(int_100_impl)
{
        int_10_impl = int_f; ++int_10_impl;
        int_ff_impl = uinteger(make_digits<traits>(2, max_digit, max_digit));
        int_100_impl = int_ff; ++int_100_impl;
}

template <typename traits>
void integer_test<traits>::test_op(int_op op, const uinteger& i1, const uinteger& i2, bool sym, size_t size, ...)
{
        va_list list;
        va_start(list, size);
        digits arr = vmake_digits<traits>(size, list);
        va_end(list);
        uinteger s = (i1.*op)(i2);
        test_equal_arr(s, arr);
        if (sym)
        {
                uinteger s = (i2.*op)(i1);
                test_equal_arr(s, arr);
        }
}

template <typename traits>
void integer_test<traits>::test_op(int_op op, const uinteger& i1, const uinteger& i2, const uinteger& r, bool sym)
{
        uinteger s = (i1.*op)(i2);
        TEST_EQUAL_INT(s, r);
        if (sym)
        {
                s = (i2.*op)(i1);
                TEST_EQUAL_INT(s, r);
        }
}

template <typename traits>
void integer_test<traits>::test()
{
        PRINT("Starting tests\n\n");
        PRINT("\n\nTesting static members...");
        test_static();
        PRINT("\n\nTesting constructors...");
        test_construct();
        PRINT("\n\nTesting increment...");
        test_increment();
        PRINT("\n\nTesting addition...");
        test_add();
        PRINT("\n\nTesting subtraction...");
        test_sub();
        PRINT("\n\nTesting relational operators...");
        test_rel();
        PRINT("\n\nTesting multiplication with a digit...");
        test_mul_digit();
        PRINT("\n\nTesting from_string operation...");
        test_from_string();
        PRINT("\n\nTesting division to a digit...");
        test_div_digit();
        PRINT("\n\nTesting to_string operation...");
        test_to_string();
        PRINT("\n\nTesting division...");
        test_div();
}

template <typename traits>
void integer_test<traits>::test_static()
{
        PRINT("Test that zero is 0");
        test_equal_digits(uinteger::zero, 1, dig_0);
        PRINT("Test that one is 1");
        test_equal_digits(uinteger::one, 1, dig_1);
}

template <typename traits>
void integer_test<traits>::test_construct()
{
        PRINT("test, that default constuctor produces 0");
        { uinteger def; TEST_EQUAL_INT(def, uinteger::zero); }

        if (max_digit == 65535)
        {
                PRINT("random tests on integers");
                { uinteger i(10u); test_equal_digits(i, 1, digit(10)); }
                { uinteger i(12345678u); test_equal_digits(i, 2, digit(24910), digit(188)); }
                PRINT("test, that double_digit -1 equals to FF");
                { test_equal_digits(int_ff, 2, max_digit, max_digit); }
                PRINT("test, that digit -1 equals to F");
                { uinteger i(digit(-1)); test_equal_digits(i, 1, max_digit); }
        }
}

template <typename traits>
void integer_test<traits>::test_increment()
{
        PRINT("test, that ++i increments by one");
        { uinteger i; i++; TEST_EQUAL_INT(i, uinteger::one); }
        PRINT("test correct behavior of POST-increment");
        { uinteger i; uinteger i2 = i++; TEST_EQUAL_INT(i2, uinteger::zero); }

        PRINT("test ++i increments by one");
        { uinteger i; ++i; TEST_EQUAL_INT(i, uinteger::one); }
        PRINT("test correct behavior of PRE-increment");
        { uinteger i; uinteger i2 = ++i; TEST_EQUAL_INT(i2, uinteger::one); }

        PRINT("test --i decrements by one");
        { uinteger i = uinteger::one; --i; TEST_EQUAL_INT(i, uinteger::zero); }
        PRINT("test i-- decrements by one");
        { uinteger i = uinteger::one; i--; TEST_EQUAL_INT(i, uinteger::zero); }

        PRINT("test, that ++i increments by one, when it should add a new digit");
        { uinteger i(max_digit); ++i; test_equal_digits(i, 2, dig_0, dig_1); }
        { uinteger i(int_ff); ++i; test_equal_digits(i, 3, dig_0, dig_0, dig_1); }

        PRINT("test 0-- equals to F");
        { uinteger i; i--; test_equal_digits(i, 1, max_digit); }
        PRINT("test, that -- on (double_digit)-1 results to 0FF");
        { uinteger i(int_ff); ++i; --i; test_equal_digits(i, 2, max_digit, max_digit); } // normalized
}

template <typename traits>
void integer_test<traits>::test_add()
{
        int_op op = &uinteger::operator +;
        bool sym = true;

        PRINT("test, that 0 + 0 == 0");
        test_op(op, uinteger::zero, uinteger::zero, uinteger::zero, sym);

        PRINT("test, that 0 + 1 == 1");
        test_op(op, uinteger::zero, uinteger::one, uinteger::one, sym);

        PRINT("test, that 1 + 1 == 2");
        test_op(op, uinteger::one, uinteger::one, uinteger((digit)2), sym);

        PRINT("test, that F + 1 == 10");
        test_op(op, int_f, uinteger::one, uinteger((unsigned int)max_digit + 1), sym);

        PRINT("test, that FF + 1 == 100");
        test_op(op, int_ff, uinteger::one, sym, 3, dig_0, dig_0, dig_1);

        PRINT("test, that 10 + 1 == 11");
        test_op(op, int_10, uinteger::one, sym, 2, dig_1, dig_1);

        PRINT("test, that 100 + 1 == 101");
        test_op(op, int_100, uinteger::one, sym, 3, dig_1, dig_0, dig_1);
}

template <typename traits>
void integer_test<traits>::test_sub()
{
        int_op op = &uinteger::operator -;
        bool sym = false;
        PRINT("test, that 0 - 0 == 0");
        test_op(op, uinteger::zero, uinteger::zero, uinteger::zero, sym);

        PRINT("test, that 1 - 1 == 0");
        test_op(op, uinteger::one, uinteger::one, uinteger::zero, sym);

        PRINT("test, that F - F == 0");
        test_op(op, int_f, int_f, uinteger::zero, sym);

        PRINT("test, that FF - FF == 0");
        test_op(op, int_ff, int_ff, uinteger::zero, sym);

        PRINT("test, that 100 - 100 == 0");
        test_op(op, int_100, int_100, uinteger::zero, sym);

        PRINT("test, that 0 - 1 == F");
        test_op(op, uinteger::zero, uinteger::one, uinteger(max_digit), sym);

        PRINT("test, that F - 1 == E");
        {
                digit d_e = max_digit; --d_e;
                test_op(op, int_f, uinteger::one, uinteger(d_e), sym);
        }

        PRINT("test, that 100 - 10 == 90");
        test_op(op, uinteger(100u), uinteger(10u), uinteger(90u), sym);

        PRINT("test, that 100 - 1 == ff");
        test_op(op, int_100, uinteger::one, int_ff, sym);

        PRINT("test, that 1 - 100 == f01");
        test_op(op, uinteger::one, int_100, sym, 3, dig_1, dig_0, max_digit);

        PRINT("test, that 0 - 100 == f00");
        test_op(op, uinteger::zero, int_100, sym, 3, dig_0, dig_0, max_digit);
}

template <typename traits>
void integer_test<traits>::test_rel(const uinteger& small, const uinteger& big)
{
        PRINT0("testing relational operations on ");
        dump_int(small);
        dump_int(big);
        PRINT("");
        TEST(small < big);
        TEST(big > small);
        TEST(big != small);
        TEST(small <= big);
        TEST(big >= small);
}

template <typename traits>
void integer_test<traits>::test_rel(const uinteger& u)
{
        PRINT0("testing relational operations on ");
        dump_int(u);
        PRINT("");
        TEST(!(u < u));
        TEST(u == u);
        TEST(u <= u);
        TEST(u >= u);
}

template <typename traits>
void integer_test<traits>::test_rel()
{
        test_rel(uinteger::zero);
        test_rel(uinteger::one);
        test_rel(int_10);
        test_rel(int_100);
        test_rel(int_f);
        test_rel(int_ff);

        test_rel(uinteger::zero, uinteger::one);
        test_rel(uinteger::zero, int_10);
        test_rel(uinteger::one, int_100);
        test_rel(uinteger::one, int_f);
        test_rel(int_f, int_ff);
        test_rel(int_f, int_10);
        test_rel(int_10, int_100);
        test_rel(int_ff, int_100);
}

template <typename traits>
void test_mul_0(const uinteger<traits>& u)
{
        TEST_EQUAL_INT(u * 0, uinteger<traits>::zero);
}

template <typename traits>
void test_mul_1(const uinteger<traits>& u)
{
        TEST_EQUAL_INT(u * 1, u);
}

template <typename traits>
void integer_test<traits>::test_mul_digit()
{
        test_mul_0(uinteger::one);
        test_mul_0(uinteger::zero);
        test_mul_0(int_f);
        test_mul_0(int_ff);
        test_mul_0(int_10);
        test_mul_0(int_100);

        test_mul_1(uinteger::one);
        test_mul_1(int_f);
        test_mul_1(int_ff);
        test_mul_1(int_10);
        test_mul_1(int_100);

        {
                uinteger x = int_10 * max_digit;
                uinteger int_f0 = int_100 - int_10;
                TEST_EQUAL_INT(x, int_f0);
        }
}

static string to_string(int x)
{
        char buf[128];
        sprintf(buf, "%u", x);
        return buf;
}

template <typename traits>
void integer_test<traits>::test_from_string_throws(const string& s)
{
        PRINT("Test that <" << s << "> makes uinteger throw");
        try
        {
                uinteger u(s);
        }
        catch (invalid_digit&)
        {
                return;
        }
        // this should never be reached
        TEST("Unreachable - Invalid digit should be detected" == 0);
}

template <typename traits>
void integer_test<traits>::test_from_string()
{
        TEST_EQUAL_INT(uinteger("0"), uinteger::zero);
        TEST_EQUAL_INT(uinteger("1"), uinteger::one);
        if (max_digit == 0xffff)
        {
                TEST_EQUAL_INT(uinteger(to_string(0xffff)), int_f);
                TEST_EQUAL_INT(uinteger(to_string(0x10000)), int_10);
                TEST_EQUAL_INT(uinteger(to_string(0xffffffff)), int_ff);
        }
        test_from_string_throws("12345670a");
        test_from_string_throws("\3");
        test_from_string_throws("^");
}

template <typename traits>
void integer_test<traits>::test_div_0(const uinteger& u)
{
        try
        {
                u / 0;
        }
        catch (division_by_zero&)
        {
                return;
        }
        // this should never be reached
        TEST("Unreachable - division to zero shall throw an assertion" == 0);
}

template <typename traits>
void integer_test<traits>::test_0_div(const uinteger& u)
{
        // 0 / x = 0
        TEST_EQUAL_INT(uinteger::zero / u, uinteger::zero);
        TEST_EQUAL_INT(uinteger::zero % u, uinteger::zero);
}

template <typename traits>
void integer_test<traits>::test_div_1(const uinteger& u)
{
        TEST_EQUAL_INT(u / 1, u);
        TEST_EQUAL_INT(u / uinteger::one, u);
        TEST_EQUAL_INT(uinteger(u % 1), uinteger::zero);
        TEST_EQUAL_INT(u % uinteger::one, uinteger::zero);
}

template <typename traits>
void integer_test<traits>::test_div_digit()
{
        test_div_0(uinteger::zero);
        test_div_0(uinteger::one);
        test_div_0(int_ff);

        test_0_div(uinteger::one);
        test_0_div(int_f);
        test_0_div(int_ff);
        test_0_div(int_10);
        test_0_div(int_100);

        test_div_1(uinteger::one);
        test_div_1(int_f);
        test_div_1(int_ff);
        test_div_1(int_10);
        test_div_1(int_100);

        TEST_EQUAL_INT(int_100 / int_f, int_10 + uinteger::one);
        TEST_EQUAL_INT(int_100 % int_f, uinteger::one);
}

template <typename traits>
void integer_test<traits>::test_string(const string& s)
{
        uinteger u1(s);
        string s2;
        u1.to_string(s2);
        PRINT("Test that <" << s << "> == <" << s2 << ">");
        TEST(s == s2);
}

struct div_test
{
        string u;
        string v;
        string q;
        string m;
};

div_test div_tests[] = {
        // and the dc collected numbers
        {
                "70655936154847220640595838297065603524466727",
                "419858591575233638596727",
                "168285078768446546944",
                "362325387671898634214439"
        },
        {
                "72772435483530073822975618566897288192073104",
                "727711039992053460527877",
                "100001829688230018208",
                "515043765454091190488688"
        },

        {
                "72767370977586703940503551828122041625737839",
                "727710187032751873999308",
                "99994987392297808678",
                "111019173099549137343015"
        },
        {
                "92256081281231",
                "133484",
                "691139621",
                "111667"
        },
        {
                "13396423706774869440",
                "5697149520",
                "2351425683",
                "5555747280",
        },
        {
                "25212385078828096299004803008522253504201083904524456857359102537909329639149514"
                "16986672165401792987173686283445255812220861952161880369999253970671005184499626"
                "92625436520072978709952998816298470113997996315285392784585306163174685595138658"
                "30767504379531164023888750038712980650207252568162460535540533733718940885053081"
                "35750337732090529711339392042867353388071500755628971900307513540009826176444936"
                "72483616984039639629110894533802261642232655728803714023477079297571707182666747"
                "04064210902895880520",
                "79383042701961504835954004931151289703975084454849535937542779898990400938374078"
                "92164641160880069183185670510212720304413721729737266755806059421573135409781876"
                "89467917097584919640997006017795641332251209610574796696390061745801226349400670"
                "2590389699",
                "31760416608728849078627528673959048360742805920869484700457407794082240534681089"
                "61585284471090236507448314491438608302635300582315333645803679212658439495390484"
                "06949554043071530141827419296363343450566001870769710104789432745039308142381295"
                "1105493034",
                "42498661367838241187363696660231848662692392614660829096011563727040135263012961"
                "61725608714887610094148468760071032160887343798695244131594617496071793999067649"
                "01749641056076041328882364479321959230560401983028401504579321501959947461842328"
                "5306023754"
        }
};

template <typename traits>
void integer_test<traits>::test_to_string()
{
        test_string("0");
        test_string("1");
        for (div_test *d = &div_tests[0]; d != ARRAY_END(div_tests); ++d)
        {
                test_string(d->u);
                test_string(d->v);
                test_string(d->q);
                test_string(d->m);
        }
}

template <typename traits>
void test_division_dc(const div_test& d)
{
        typedef uinteger<traits> uinteger;
        const uinteger ui(d.u);
        const uinteger vi(d.v);
        const uinteger qi(d.q);
        const uinteger mi(d.m);

        uinteger q1;
        uinteger m1 = ui.divmod(vi, q1);

        TEST_EQUAL_INT(q1, qi);
        TEST_EQUAL_INT(m1, mi);
}

template <typename traits>
void integer_test<traits>::test_div()
{
        TEST_EQUAL_INT(int_100 / int_ff, uinteger::one);
        TEST_EQUAL_INT(int_100 % int_ff, uinteger::one);
        TEST_EQUAL_INT(int_100 / int_10, int_10);
        TEST_EQUAL_INT(int_100 % int_10, uinteger::zero);

        for (div_test *d = &div_tests[0]; d != ARRAY_END(div_tests); ++d)
        {
                test_division_dc<traits>(*d);
        }
}
